/*
 * @lc app=leetcode.cn id=1 lang=javascript
 *
 * [1] 两数之和
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */


// 二分查找第二个值的下标
/**
 * 新建下标数组
 * 按nums大小对下表树组排序
 */
const binary_search = function(nums, indexs, target, i){
  let head = i + 1, tail = indexs.length - 1, mid;
  while(head <= tail){
    mid = head + ((tail - head) >> 1);
    if(nums[indexs[mid]] === target) return indexs[mid];
    if(nums[indexs[mid]] < target){
      head = mid + 1;
    } else {
      tail = mid - 1;
    }
  }
  return -1;
}
var twoSum = function(nums, target) {
  let indexs = [];
  for (let i = 0; i < nums.length; i++) indexs[i] = i;
    
  indexs.sort((a,b)=> nums[a] - nums[b]);

  for(let i = 0; i < indexs.length; i++){
    let j = binary_search(nums, indexs, target - nums[indexs[i]], i);
    if(j != -1) return [indexs[i], j];
  }
};

// var twoSum = function(nums, target) {
//   let map = new Map();
//   for (let i = 0; i < nums.length; i++) {
//     // nums[i]为结果的第二个值时，查看map中是否已有第一个值
//     if(map.has(target - nums[i])){ 
//       return [map.get(target - nums[i]),i];
      
//     // nums[i]为结果的第一个值时，会放入map中
//     } else {
//       map.set(nums[i], i)
//     }
//   }
// };

/**
 * 复习 2021-08-04
 */
// var dfs = function(nums, target, start){
//   for (let i = start + 1; i < nums.length; i++) {
//     if(nums[i] == target-nums[start]) return i;
//   }
//   return false;
// }
// var twoSum = function(nums, target) {
//   for (let i = 0; i < nums.length; i++) {
//     let second = dfs(nums, target, i);
//     if(second) return [i, second];
//   }
// }


// @lc code=end

